#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
using T = int;
T rad(); // quick read
const int inf = 0x3f3f3f3f;
#define rf(i, n) for (int i = 1; i <= (n); ++i)
const int max_size = 40; // fi size
const int maxn = 5 + 1e7;

const int mod = 998244353;

int f[max_size];
ll pre[max_size];
int fsiz;
inline void init_fi() {
    f[++fsiz] = 1, pre[fsiz] = 1;
    while (f[fsiz] < maxn) {
        ++fsiz, f[fsiz] = f[fsiz - 1] + f[fsiz - 2];
        pre[fsiz] = pre[fsiz - 1] + f[fsiz];
    }
}

int dfs_mem[max_size][maxn];

int dfs(int i, int j) {
    if (j == 0) return 1;                    // 边界
    if (j < 0 || i < 0) return 0;            // 非法
    if (dfs_mem[i][j]) return dfs_mem[i][j]; // 记忆化
    if (pre[i] < j) return 0;                // 剪枝 1
    ll ret = 0;
    for (int k = lower_bound(pre + 1, pre + 1 + i, j) - pre; k <= i; ++k) { // 剪枝 2
        if (f[k] > j) break;                                                // 剪枝 3
        ret += (ll)f[k] * dfs(k - 1, j - f[k]) % mod;
    }

    return dfs_mem[i][j] = ret % mod;
}

int main() {
    init_fi();
    int Q = rad();
    while (Q--) {
        int x = rad();
        printf("%d\n", dfs(fsiz, x));
    }
}

T rad() {
    T back = 0;
    int ch = 0, posi = 0;
    for (; ch < '0' || ch > '9'; ch = getchar())
        posi = ch ^ '-';
    for (; ch >= '0' && ch <= '9'; ch = getchar())
        back = (back << 1) + (back << 3) + (ch & 0xf);
    return posi ? back : -back;
}